package top.minuy.algorithm.search.binary;

/**
 * 二分搜索算法
 * 针对有序数组
 * 可以实现快速搜索指定元素
 * 可以实现实现快速搜索大于指定元素的最小的值
 * 可以实现实现快速搜索小于指定元素的最大的值
 * 涉及到递归算法
 *
 * @author Minuy
 * @time 13:44
 * @date 2021/9/2
 */
public class BinarySearch {
    private BinarySearch() {
    }

    public static <E extends Comparable<E>> int lower(E[] arr, E target) {
        int l = -1, r = arr.length - 1, m;
        // int s = 0;
        // 在[l,r]中查找，l不是数组元素，但是是合法解，表示小于此的最大值在数组的左边
        while (l < r) {
            // 关键在这里，每次除法的时候不应该是去除小数部分，而是有小数部分就加1
            // 这样才能让r动
            m = (l + (int) ((r - l) / 2)) < (l + (r - l) / 2.0) ? (l + (r - l) / 2 + 1) : (l + (r - l) / 2);
            System.out.println();
            if (target.compareTo(arr[m]) > 0) { // 小于
                // int bl = l;
                l = m;
                // out(String.format("第%d次循环，l : %d -> %d, r : %d，(m : index = %d, val = %s) %s (target : %s)", ++s, bl, l, r, m, arr[m], "<=", target));
            } else { // 大于等于
                // int br = r;
                r = m - 1;
                // out(String.format("第%d次循环，l : %d, r : %d -> %d，(m : index = %d, val = %s) %s (target : %s)", ++s, l, br, r, m, arr[m], ">", target));
            }

//            if(s>20){
//                break;
//            }
        }
        return l;
    }

    public static <E extends Comparable<E>> int lower_ceil(E[] arr, E target) {
        int lower = lower(arr, target);
        if ((lower + 1) < arr.length && arr[lower + 1].compareTo(target) == 0) {
            return lower + 1;
        }
        return upper(arr, target);
    }

    public static <E extends Comparable<E>> int up_ceil(E[] arr, E target) {
        int upper = upper(arr, target);
        // 要确保upper-1是合法的
        if ((upper - 1) > 0 && arr[upper - 1].compareTo(target) == 0) {
            return upper - 1;
        } else {
            return upper;
        }
    }

    /**
     * 在从小到大排好序的数组中寻找大于target的最小值
     *
     * @param arr    目标数组
     * @param target 目标值
     * @param <E>    泛型支持
     * @return 大于target的第一个值的索引
     */
    public static <E extends Comparable<E>> int upper(E[] arr, E target) {
        int l = 0, r = arr.length, m;

        // int s = 0;
        // 在[l,r]中查找，r不是数组元素，但是是合法解，表示大于此的最小值在数组的右边
        while (r > l) {
            m = l + (r - l) / 2;
            if (arr[m].compareTo(target) > 0) {
                // int br = r;
                r = m;
                // out(String.format("第%d次循环，l : %d, r : %d -> %d，(m : index = %d, val = %s) %s (target : %s)", ++s, l, br, r, m, arr[m], ">", target));
            } else {
                // int bl = l;
                l = m + 1;
                // out(String.format("第%d次循环，l : %d -> %d, r : %d，(m : index = %d, val = %s) %s (target : %s)", ++s, bl, l, r, m, arr[m], "<=", target));
            }
        }

        return l;
    }

    private static void out(String s) {
        System.out.println(s);
    }

    public static <E extends Comparable<E>> int search(E[] data, E target) {
        return search(data, target, 2);
    }

    public static <E extends Comparable<E>> int search(E[] data, E target, int v) {
        if (v == 1) {
            return search(data, target, 0, data.length);
        } else {
            int l = 0, r = data.length, m;
            // 没有找到时退出循环，返回-1
            while (l < r) {
                m = l + (r - l) / 2;
                if (data[m].compareTo(target) == 0) {
                    return m;
                } else if (data[m].compareTo(target) > 0) {
                    r = m;
                } else {
                    l = m + 1;
                }
            }
            return -1;
        }
    }

    // [l,r)
    private static <E extends Comparable<E>> int search(E[] data, E target, int l, int r) {
        // 等于的时候也要返回，此时区间没了元素了
        if (l >= r) {
            return -1;
        }
        int m = l + (r - l) / 2;
        if (data[m].compareTo(target) == 0) {
            return m;
        } else if (data[m].compareTo(target) > 0) {
            return search(data, target, l, m);
        } else {
            return search(data, target, m + 1, r);
        }
    }
}
